﻿#pragma once
#include<iostream>
#include<vector>
using namespace std;

//HashData的状态
enum State
{
	EXIST,//存在
	DELETE,//删除
	EMPTY //空
};

//定义HashData
template<class K,class V>
struct HashData
{
	pair<K, V> _kv;
	State _state = EMPTY;
};

//默认仿函数模板（解决key不为无符号整形问题）
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
//特化
template<>
struct HashFunc<string>
{
/*
字符串转换成整形，可以把字符ascii码相加即可
但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的 
这⾥我们使⽤BKDR哈希的思路，⽤上次的计算结果去乘以⼀个质数，这个质数⼀般去31, 131等效果会⽐较好
*/ 
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto ch : key)
		{
			hash *= 131;
			hash += ch;
		}
		return hash;
	}
};

//定义HashTable
template<class K,class V,class Hash= HashFunc<K>>
class HashTable
{
public:
	//素数表
	inline unsigned long __stl_next_prime(unsigned long n)
	{
		// Note: assumes long is at least 32 bits.
		static const int __stl_num_primes = 28;
		static const unsigned long __stl_prime_list[__stl_num_primes] =
		{
			53, 97, 193, 389, 769,
			1543, 3079, 6151, 12289, 24593,
			49157, 98317, 196613, 393241, 786433,
			1572869, 3145739, 6291469, 12582917, 25165843,
			50331653, 100663319, 201326611, 402653189, 805306457,
			1610612741, 3221225473, 4294967291
		};
		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list + __stl_num_primes;
		const unsigned long* pos = lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;
	}
	//构造
	HashTable()
		:_tables(__stl_next_prime(0))
		,_n(0)
	{}
	//插入
	bool Insert(const pair<K, V>& kv)
	{
		//if (_n * 10 / _tables.size() > 7)//负载因子大于0.7进行扩容
		//{
		//	vector<HashData<K, V>>  newTables(_tables.size()*2);//定义2倍新表
		//	for (int i = 0; i < _tables.size(); i++)//遍历旧表元素映射到新表
		//	{
		//		if (_tables[i]._state == EXIST)//旧表中元素存在走插入逻辑
		//		{
		//			size_t hashi = _tables[i]._kv.first % newTables.size();//初始映射位置
		//			while (newTables[hashi]._state == EXIST)//找到一个删除位置或空位置
		//			{
		//				hashi++;//一次线性探测
		//				hashi %= newTables.size();//如果走到表尾进行回绕继续寻找
		//			}
		//			newTables[hashi]._kv = _tables[i]._kv;
		//			newTables[hashi]._state = EXIST;
		//			//只是单纯的重新映射，不需要增加有效个数
		//		}
		//	}
		//	_tables.swap(newTables);//交换新旧表
		//}
		if (Find(kv.first)) return false;
		if (_n * 10 / _tables.size() > 7)//负载因子大于0.7进行扩容
		{
			HashTable<K, V> newht;//定义2倍新表
			newht._tables.resize(__stl_next_prime((unsigned long)_tables.size()+1));
			for (auto& e:_tables)//遍历旧表元素映射到新表
			{
				if (e._state == EXIST)//旧表中元素存在走插入逻辑
				{
					newht.Insert(e._kv);//复用插入代码
				}
			}
			_tables.swap(newht._tables);//交换新旧表
		}
		Hash hs;
		size_t hashi = hs(kv.first) % _tables.size();//初始映射位置
		while (_tables[hashi]._state==EXIST)//找到一个删除位置或空位置
		{
			hashi++;//一次线性探测
			hashi %= _tables.size();//如果走到表尾进行回绕继续寻找
		}
		_tables[hashi]._kv = kv;
		_tables[hashi]._state = EXIST;
		++_n;//别忘了有效个数++
		return true;
	}
	//查找
	HashData<K,V>* Find(const K& key)
	{
		Hash hs;
		size_t hashi = hs(key) % _tables.size();
		while (_tables[hashi]._state != EMPTY)//如果映射值存在或删除则进入循环进行判断
		{
			//如果映射值存在并且key相等，则返回该位置的指针
			if (_tables[hashi]._state == EXIST &&
				key == _tables[hashi]._kv.first)
				return &_tables[hashi];
			hashi++;
			hashi %= _tables.size();
		}
		return nullptr;
	}
	//删除
	bool Erase(const K& key)
	{
		HashData<K, V>* pos = Find(key);
		if (pos == nullptr) return false;
		else
		{
			(*pos)._state = DELETE;//状态置为删除即可
			_n--;//有效个数减一
		}
		return true;
	}
private:
	size_t _n=0;//记录哈希表中有效数据的个数
	vector<HashData<K, V>>  _tables;
};



